#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
/*
 * @lc app=leetcode.cn id=212 lang=cpp
 *
 * [212] 单词搜索 II
 */

// @lc code=start
int dxdy[2][4] = {
        {0, 0, 1, -1},
        {1, -1, 0, 0}
};

struct TriesNode {
    string word;
    unordered_map<char, TriesNode*> children;
    TriesNode(): word("") {
    }
};

void insertString(TriesNode* root, const string &s) {
    for (char x: s) {
        if (!root->children.count(x)) root->children[x] = new TriesNode();
        root = root->children[x];
    }
    root->word = s;
}

class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        TriesNode *root = new TriesNode();
        for (int i = 0; i < words.size(); i++) {
            insertString(root, words[i]);
        }

        vector<string> res;
        int m = board.size(), n = board[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(root, i, j, board, res);
            }
        }
        return res;
    }

    void dfs(TriesNode* root, int x, int y, vector<vector<char>>& board, vector<string>& res) {
        char now = board[x][y];
        if (!root->children[now]) return;
        root = root->children[now];
        if (root->word.size() > 0) {
            res.push_back(root->word);
            root->word = "";
        }
        
        board[x][y] = '-';
        for (int i = 0; i < 4; i++) {
            int nx = x + dxdy[0][i], ny = y + dxdy[1][i];
            if (nx >= 0 && nx < board.size() && ny >= 0 && ny < board[0].size() && board[nx][ny] != '-') {
                dfs(root, nx, ny, board, res);
            }
        }
        board[x][y] = now;
    } 
};
// @lc code=end

